package com.czk.tree.huffmantree.huffmanpractice;

import lombok.Data;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈夫曼树的创建
 *
 * @Author:ChenZhangKun
 * @Date: 2020/11/12 21:07
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] array = {1, 58, 4, 5, 7, 3, 9, 24, 2};
        Node huffmanTree = createHuffmanTree(array);
        huffmanTree.preTraverse();
    }

    /**
     * 创建哈夫曼树方法
     *
     * @param array
     * @return
     */
    public static Node createHuffmanTree(int[] array) {
        // 将各个节点创建node
        List<Node> list = new ArrayList<>(10);
        for (int i : array) {
            Node node = new Node(i);
            list.add(node);
        }
        // 排序，实现了cpmparable接口
        Collections.sort(list);
        // 创建Huffman
        while (list.size() > 1) {
            // 拿到第一个
            Node node = list.get(0);
            // 拿到第二个
            Node node1 = list.get(1);
            // 创建新的节点
            Node parent = new Node(node.getValue() + node1.getValue());
            parent.setLeft(node);
            parent.setRight(node1);
            // 移除第一个和第二个
            list.remove(node);
            list.remove(node1);
            // 将其放入集合
            list.add(parent);
            // 重新排序
            Collections.sort(list);
        }
        return list.get(0);
    }
}

@Data
class Node implements Comparable<Node> {
    /**
     * 权值
     */
    private Integer value;
    /**
     * 左节点
     */
    private Node left;
    /**
     * 右节点
     */
    private Node right;

    public Node(Integer value) {
        this.value = value;
    }

    /**
     * @param o
     * @return
     */
    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }

    public void preTraverse() {
        System.out.println(this.value);
        if (this.left != null) {
            this.left.preTraverse();
        }
        if (this.right != null) {
            this.right.preTraverse();
        }
    }
}
